package com.summli.basic.class08;

/**
 * 给定一棵二叉树的头节点head，任何两个节点之间都存在距离，
 * 返回整棵二叉树的最大距离
 */
public class Code08_MaxDistance {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    //主要是如何定义返回的信息
    public static class Info{
        private int maxDistance;//返回的子树的最大距离
        private int height;//子树的高度

        public Info(int maxDistance,int height){
            this.height = height;
            this.maxDistance = maxDistance;
        }
    }

    public static int maxDistance2(Node head) {
        return process(head).maxDistance;
    }

    private static Info process(Node node) {
        if(node == null){
            return new Info(0,0);
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        int maxDistance = Math.max(Math.max(leftInfo.maxDistance,rightInfo.maxDistance),leftInfo.height+rightInfo.height+1);
        int height = Math.max(leftInfo.height, rightInfo.height);
        return new Info(maxDistance,height+1);
    }
}
